\documentclass[a4paper]{article}
\usepackage[italian]{babel}

\begin{document}
\section{Inquadramento del problema}
Siano $I_1$ e $I_2$ due immagini di dimensione $m\times n$, $I_2$
ottenuta traslando ciaoscun pixel $(i,j)$ della matrice $I_1$  di uno
spostamento $\vec h_{ij}=(u_{ij},v_{ij})$.
Vogliamo trovare due matrici $U=(u_{ij})$ e $V=(v_{ij})$ di
spostamento risp. verticale e orizzontale che minimizzino il
funzionale $E$ per determinare lo spostamento dei pixel dall'immagine
$I_1$ all'immagine $I_2$.
\begin{eqnarray}
  \label{eq:energia}
\nonumber  E(U,V) &= & \displaystyle\sum_{ij} \Big( I_1(i,j) -
I_2(i+u_{ij},j+v_{ij}) \Big)^2\\
\nonumber  &+  & \displaystyle\sum_{ij} g\Big( ||\vec h_{ij}- \vec
         h_{i+1,j} || \Big)\\
\nonumber &+  & \displaystyle\sum_{ij} g\Big( ||\vec h_{ij}- \vec
         h_{i,j+1} || \Big)
\end{eqnarray}

L'intento e' di minimizzare questa funzione energia in modo da
determinare lo spostamento di ciascun pixel. Le sommatorie in cui
figura le $g$ servono a fare in modo che lo spostamento dei pixel
adiacenti sia dello stesso tipo.


\section{Spazio degli spostamenti}
Indichiamo con $R_{ij}$ lo spazio dei possibili spostamenti del pixel
$(i,j)$. Tale spazio dipende da pixel a pixel (per via dalla distanza
del pixel dai bordi).
Se supponiamo che le componenti dello spostamento del pixel varino tra
$-1$ e $1$, allora per i pixel che non sono adiacenti al bordo
dell'immagine lo spazio degli spostaenti \`e dato da
$$
  R_{ij}= \{-1,0,1\}^2,
$$
ossia
$$
\vec h_{ij}\in\{(0,0),(0,1),\ldots,(-1,0),(-1,1),(-1,-1)\}.
$$

\section{Ottimizzazione del calcolo dell'energia}
Ogni formica effettua una scelta di un elemento $\vec h_{ij}\in
R_{ij}$ per ogni pixel $(i,j)$ dell'immagine determina la bont\`a di
tale soluzione calcolandone l'energia.

La computazione di questa energia \`e lenta per via dei termini delle
sommatorie con la funzione $g$. La $g$ viene calcolata sulle
differenze di tutte le combinazioni dei vettori spostamento, i le
quali sono in numero finito in questo finiti sono i possibili
spostamenti. Supponendo di avere uno spostamento massimo di valore
$M$, allora conviene salvare i valori della $g$ in una tabella di hash
indicizzata sulle coppie dell'insieme
$$
\{(h,k)|h,k=0,\ldots,M,\ h\geq k\}.
$$
A ciascuna coppia \`e assegnato il valore $g(||(h,k)||)$. Non serve
considerare tutte le combinazioni di $h$ e $k$ in quanto $g$ diepnde
solo dalla norma del vettore a cui \`e applicata.

La dimensione massima della tabella di hash \`e di al pi\`u $M(2M+1)$
elementi su cui calcolare la $g$. Tale tabella di hash pu\`o essere
totalmente generata all'inizio dell'algoritmo oppure in maniera
dinamica durante l'esecuzione stessa dell'algoritmo, semplicemente
aggiungendo alla tabella di hash il vettore e il suo valore della
$g$. 

Chiamiamo questa tabella di hash $G$.

\section{Matrice del feromone}
Gestiamo la deposizione del feromone in una matrice $PH$
della stessa dimensione dell'immagine, le cui entrate 
$PH(i,j)$ sono costituite da una tabella di hash dei valori di 
feromone depositato su ciscun sostamento indicizzata sui possibili
spostamenti $\vec h_{ij}\in R_{ij}$.

All'inizio dell'algoritmo tutte queste tabelle di hash saranno vuote,
e verranno costruite dinamicamente durante la valutazione di ogni
soluzione: per ogni scelta dello spostamento del pixel la formica
aggiorna il feromone depositato su tale spostamento, aggiungendo lo
spostamento stesso alla tabella di hash nel caso questo non sia gi\`a
stato utilizzato nell'algoritmo.

\section{Costruzione della soluzione}
Ciascuna formica effettua una scelta $\vec h_{ij}\in R_{ij}$ per ogni
pixel $(i,j)$ dell'immagine. Valutata la bont\`a di tale soluzione
(ossia l'energia) va a depositare una quantit\`a $\varphi$ di feromone
(dipendente dalla bont\`a della soluzione)
sullo spostamento corrispondente della tabella di hash dell'entrata
$(i,j)$ della matrice $PH$.

La tabella di hash di ogni pixel viene generata in maniera dinamica al
procedere dell'algoritmo, per non occupare troppa memoria.

\subsection{Scelta dello spostamento al pixel $(i,j)$}
Al momento di effettuare la scelta, la formica si trova ad avere $N$
possibili spostamenti gi\`a effettuati, ciascuno con il proprio valore
di feromone.
La tabella di hash sar\`a costituita dai valori (coppia chiave/valore)
$$
(\vec h^1_{ij},p^1_{ij}),(\vec h^2_{ij},p^2_{ij}),\ldots,(\vec
h^N_{ij},p^N_{ij}). 
$$

La formica deve scegliere tra questi $N$ spostamenti gi\`a valutati,
in base alla quantit\`a di feromone di ciascuno spostamento, e con una
certa probabilit\`a deve avere la possibilit\`a di scegliere tra
spostamenti che non sono presenti sulla tabella di hash.

\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
